/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/find-leaves-of-binary-tree
   @Language: C++
   @Datetime: 19-03-29 16:13
   */

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

// Method 1, Time O(n*h), Space O(1), Time 435ms
class Solution {
	vector<int> v;
	void preorder(TreeNode *root, TreeNode *fa){
		if (root==NULL) return;
		if (root->left==NULL && root->right==NULL){
			v.push_back(root->val);
			if (fa) fa->left==root?fa->left=NULL:fa->right=NULL;
			return;
		}
		preorder(root->left,root);
		preorder(root->right,root);
	}
public:
	/*
	 * @param root: the root of binary tree
	 * @return: collect and remove all leaves
	 */
	vector<vector<int>> findLeaves(TreeNode * root) {
		// write your code here
		vector<vector<int> > vs;
		while(root){
			if (root->left==NULL && root->right==NULL){
				vs.push_back({root->val});
				break;
			}
			v.clear();
			preorder(root,NULL);
			vs.push_back(v);
		}
		return vs;
	}
};


// Method 2, Time O(n), Space O(1), Time 260ms
class Solution {
	int postorder(TreeNode *root, vector<vector<int> > &vs){
		if (root==NULL) return 0;
		int left=postorder(root->left,vs);
		int right=postorder(root->right,vs);
		int depth=max(left,right)+1;
		if(vs.size()<depth) vs.push_back({root->val});
		else vs[depth-1].push_back(root->val);
		return depth;
	}
public:
	/*
	 * @param root: the root of binary tree
	 * @return: collect and remove all leaves
	 * Tip:
	 * calculate each node to leaf maximum path, same path node is leaf
	 */
	vector<vector<int>> findLeaves(TreeNode * root) {
		// write your code here
		vector<vector<int> > vs;
		postorder(root, vs);
		return vs;
	}
};
